# -*- coding: utf-8 -*- 
# @project : 《Atcoder》
# @Author : created by bensonrachel on 2022/2/21
# @File : 567. 字符串的排列.py

#字节（模拟笔试）第二题。

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        """
        s1 的排列之一是 s2 的 子串(必须连续)且s1不会变。排列不讲究顺序，但是字符出现的 种类 和 次数 要恰好对应相等。
        """
        ls1 = len(s1)  # 获取两个字符串的长度，后面要用做固定长度的滑动窗口。
        ls2 = len(s2)
        if ls1 > ls2:
            return False  # 如果s1比s2还要长，那就不需要往下直接判断s1 的排列之一不可能是 s2 的 子串。
        else:  # 如果s1比s2短，或相等。
            s1_line = [0] * (30)
            s2_line = [0] * (30)
            # 用数组s1_line装载s1中每个字符的数量（使用ASCII码-'a'作为数组的下标）（不会变的）。
            # 而数组s2_line装载的是固定长度的在s2上从头开始滑动的滑动窗口的每个字符的数量（会动态变化）
            for s in s1:
                s1_line[ord(s) - ord('a')] += 1
            for i in range(ls1):
                s2_line[ord(s2[i]) - ord('a')] += 1
            # 滑动窗口的初始位置是需要特殊处理的，为了后面一增一减时只需要统计增的和减的字符即可。
            S = set()  # 用set的去重性质来装需要比较的s1和s2的滑动子串的数量不相等的字符。如果相等了的就移除。

            # 不仅s2的子串的与s1的不相等的字符需要加入S
            for s in s2[:ls1]:
                if s2_line[ord(s) - ord('a')] != s1_line[ord(s) - ord('a')]:
                    S.add(s)
            # 而且s1的与s2的子串的不相等的字符也需要加入S，为了保证后面的统一和操作方便。（避免需要移除本来就不在set里的元素）
            # 因为不论增还是减的字符，都有可能是导致不相等或者相等。
            for s in s1:
                if s1_line[ord(s) - ord('a')] != s2_line[ord(s) - ord('a')]:
                    S.add(s)

            if len(S) == 0:  # 别忘了初始位置也是需要判断一下s1的每个字符数量符合不符合与s2初始位置的子串的每个字符的数量都是相等。
                return True
            # 开始滑动，每次向后移动一个位置，窗口大小是固定的长度为ls1。
            for i in range(1, ls2 - ls1 + 1):
                j = i + ls1 - 1
                # 每次只需要处理增的字符和减的字符的数量即可。
                s2_line[ord(s2[i - 1]) - ord('a')] -= 1
                s2_line[ord(s2[j]) - ord('a')] += 1
                # 如果一增一减的字符是相同的，等于对滑动窗口中的每个字符的数量没有任何影响。则不需要处理。
                if s2[i - 1] != s2[j]:  # 只处理不相等的情况：
                    if s2_line[ord(s2[i - 1]) - ord('a')] == s1_line[ord(s2[i - 1]) - ord('a')]:
                        S.remove(s2[i - 1])  # 减少导致相等
                    if s2_line[ord(s2[i - 1]) - ord('a')] != s1_line[ord(s2[i - 1]) - ord('a')]:
                        S.add(s2[i - 1])  # 减少导致不相等
                    if s2_line[ord(s2[j]) - ord('a')] != s1_line[ord(s2[j]) - ord('a')]:
                        S.add(s2[j])  # 增加导致不相等
                    if s2_line[ord(s2[j]) - ord('a')] == s1_line[ord(s2[j]) - ord('a')]:
                        S.remove(s2[j])  # 增加导致相等
                if len(S) == 0:  # 如果遇到set为空了，则说明此时的滑动窗口子串与s1没有数量不相等的字符，则说明符合条件。
                    return True
            return False
